package 剑指offer;

/**
 * @author: tyy 剑指 Offer II 069. 山峰数组的顶部 查找山峰顶部
 * 符合下列属性的数组 arr 称为 山峰数组（山脉数组） ：
 *
 * arr.length >= 3
 * 存在 i（0 < i < arr.length - 1）使得：
 * arr[0] < arr[1] < ... arr[i-1] < arr[i]
 * arr[i] > arr[i+1] > ... > arr[arr.length - 1]
 * 给定由整数组成的山峰数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i ，即山峰顶部。
 * 示例 1：
 * 输入：arr = [0,1,0]
 * 输出：1
 * @create: 2021-10-14 17:40
 * @description:
 **/
public class Solution1 {


    public int peakIndexInMountainArray1(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i+1]) {
                return i;
            }
        }
        return 0;
    }

    /** 二分法
     * @param arr
     * @return
     */
    public int peakIndexInMountainArray2(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while(left < right){
            int middle = (left + right) / 2;
            if(arr[middle] > arr[middle-1] && arr[middle] > arr[middle+1]){     // 比左右元素大则返回
                return middle;
            }
            else if(arr[middle] > arr[middle-1] && arr[middle] < arr[middle+1]){ // 比左元素大右元素小则把mid赋值给left，缩小计算范围并防止死循环
                left = middle;
            }
            else{
                right = middle; // arr[middle] < arr[middle-1] 查找范围左移
            }
        }
        return 0;
    }
    public int peakIndexInMountainArray2_1(int[] arr) {
        int left = 0;
        int right = arr.length-1;
        int mid = 0;
        while(left<=right){
            mid = left+(right-left)/2;  // ==>(left + right) / 2;
            if(arr[mid]>arr[mid+1]&&arr[mid]>arr[mid-1]) { // 峰顶元素arr[mud]
                break;                  // 很聪明直接跳出循环
            }else if (arr[mid]>arr[mid+1]){ // ==》&&arr[mid]<arr[mid-1] 继续二分查找，mid元素大于右元素缩小范围
                right = mid-1;
            }else{
                left = mid+1; // 则left需要在mid基础上加1，防止死循环
            }

            /*else if (arr[mid]>arr[mid-1]){ // ==》&&arr[mid]<arr[mid+1] 继续二分查找，mid元素大于左元素缩小范围
                left = mid+1;
            }else{
                right = mid-1;
            }*/
        }
        return mid;
    }
    public int peakIndexInMountainArray2_2(int[] arr) {
        int left = -1;
        int right = arr.length;
        int mid = (left + right) / 2; // 可以与循环里合成一个
        while (left + 1 != right) {
            if (arr[mid + 1] > arr[mid]) {
                left = mid;
            } else {
                right = mid;
            }
            mid = (left + right) / 2;
        }
        return right;
    }

    /** 双指针打个卡
     * @param arr
     * @return
     */
    public int peakIndexInMountainArray(int[] arr) {
        int low = 0, hight = arr.length - 1;

        while (low++ <= hight--) {
            if (arr[low] < arr[low - 1]) {
                return low - 1;
            } else if (arr[hight] < arr[hight + 1]) {
                return hight + 1;
            }
        }

        return -1;
    }
    public static void main(String[] args) {
        int[] arr = {0, 5,4,3,2, 0};
        int i = 0;
        i = new Solution1().peakIndexInMountainArray2_1(arr);
        System.out.println("i = " + i);
        int arr2[] = {1,3,5,4,2};
        i = new Solution1().peakIndexInMountainArray2_1(arr2);
        System.out.println("i = " + i);
        int arr3[] = {0,1,3,5,10,5,2};
        i = new Solution1().peakIndexInMountainArray2_1(arr3);
        System.out.println("i = " + i);
    }
}

